#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 006. Z 字形变换.py
@time: 2021/12/16 13:23
@desc: https://leetcode-cn.com/problems/zigzag-conversion/
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
@解题思路：
    1. 按行排序: 通过从左向右迭代字符串，我们可以轻松地确定字符位于 Z 字形图案中的哪一行。 t: O(n), s: O(n)
'''

# TODO
class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if len(s) == 1 or numRows==1 or numRows>len(s):
            return s
        n = len(s)

        bc = numRows
        sc = bc - 2
        # 计算有几个z
        if n>(bc+sc):
            col_len = n // (bc + sc) * (1 + sc) + n % (bc + sc)
        else:
            col_len = 1 + n - numRows

        a = [[' ' for c in range(col_len)] for row in range(numRows)]

        row, col = 0, 0
        for i in range(n):
            if i % (bc+sc) < numRows:
                if i % (bc+sc) == 0:
                    row = 0
                a[row][col] = s[i]
                row += 1
                if row == numRows:
                    row = numRows - 2
                    col += 1
            else:
                a[row][col] = s[i]
                col += 1
                row -= 1
        res = ''
        for i in range(numRows):
            str = ''.join(a[i]).split(' ')
            str = ''.join(str)
            res = res + str

        return res

if __name__ == '__main__':
    s = "PAYPALISHIRING"
    numRows = 5
    res = Solution().convert(s, numRows)
    print(res)